package com.wjk.test;

/**
 * @author : RobertWei
 * time: 2021/9/23    17:30
 * description:
 */

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0){
            return "";
        }
        int[] need = new int[128];

        //记录需要的字符的个数
        for (int i = 0; i < t.length(); i++) {
            need[t.charAt(i)]++;
        }

        //l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
        int left = 0, right = 0, size = Integer.MAX_VALUE, count = t.length(), start = 0;

        //遍历所有字符
        while (right < s.length()) {

            char c = s.charAt(right);

            if (need[c] > 0) {
                //需要字符c
                count--;
            }

            //把右边的字符加入窗口
            need[c]--;

            //窗口中已经包含所有字符
            if (count == 0) {
                while (left < right && need[s.charAt(left)] < 0) {
                    //释放左边移动出窗口的字符
                    need[s.charAt(left)]++;
                    left++;//指针右移
                }

                //不能右移时候挑战最小窗口大小，更新最小窗口开始的start
                if (right - left + 1 < size) {
                    size = right - left + 1;
                    //记录下最小值时候的开始位置，最后返回覆盖串时候会用到
                    start = left;
                }

                //l向右移动后窗口肯定不能满足了 重新开始循环
                //左移时去除的有效字符 加一
                need[s.charAt(left)]++;
                //左指针右移一位
                left++;
                //有效字符总数量加一
                count++;
            }

            right++;
        }
        return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
    }
}
